/*-------------------------------------------------------------------------
 * unicode_norm.c
 *		规范化Unicode字符串
 *
 * 这实现了Unicode标准化，依照文档
 * https://www.unicode.org/reports/tr15/。
 *
 * Portions Copyright (c) 2017-2022, PostgreSQL Global Development Group
 *
 * IDENTIFICATION
 *	  src/common/unicode_norm.c
 *
 *-------------------------------------------------------------------------
 */
#ifndef FRONTEND
#include "postgres.h"
#else
#include "postgres_fe.h"
#endif

#include "common/unicode_norm.h"
#ifndef FRONTEND
#include "common/unicode_norm_hashfunc.h"
#include "common/unicode_normprops_table.h"
#include "port/pg_bswap.h"
#else
#include "common/unicode_norm_table.h"
#endif

#ifndef FRONTEND
#define ALLOC(size) palloc(size)
#define FREE(size) pfree(size)
#else
#define ALLOC(size) malloc(size)
#define FREE(size) free(size)
#endif

/* 处理与韩文字母相关的计算的常量 */
#define SBASE		0xAC00		/* U+AC00 */
#define LBASE		0x1100		/* U+1100 */
#define VBASE		0x1161		/* U+1161 */
#define TBASE		0x11A7		/* U+11A7 */
#define LCOUNT		19
#define VCOUNT		21
#define TCOUNT		28
#define NCOUNT		VCOUNT * TCOUNT
#define SCOUNT		LCOUNT * NCOUNT

#ifdef FRONTEND
/* bsearch() 的分解查找表的比较例程。 */
static int fc_conv_compare(const void *fc_p1, const void *fc_p2)
{
	uint32		fc_v1,
				fc_v2;

	fc_v1 = *(const uint32 *) fc_p1;
	fc_v2 = ((const pg_unicode_decomposition *) fc_p2)->codepoint;
	return (fc_v1 > fc_v2) ? 1 : ((fc_v1 == fc_v2) ? 0 : -1);
}

#endif

/*
 * get_code_entry
 *
 * 获取与分解查找表中代码对应的条目。
 * 该代码的后端版本使用完美哈希函数进行查找，而前端版本使用二分查找。
 */
static const pg_unicode_decomposition *
fc_get_code_entry(pg_wchar fc_code)
{
#ifndef FRONTEND
	int			fc_h;
	uint32		fc_hashkey;
	pg_unicode_decompinfo fc_decompinfo = UnicodeDecompInfo;

	/*
	 * 计算哈希函数。哈希键是具有网络顺序的字节的代码点。
	 */
	fc_hashkey = pg_hton32(fc_code);
	fc_h = fc_decompinfo.hash(&fc_hashkey);

	/* 超出范围的结果表示没有匹配 */
	if (fc_h < 0 || fc_h >= fc_decompinfo.num_decomps)
		return NULL;

	/*
	 * 由于这是一个完美哈希，我们只需要与其标识的特定代码点匹配。
	 */
	if (fc_code != fc_decompinfo.decomps[fc_h].codepoint)
		return NULL;

	/* 成功！ */
	return &fc_decompinfo.decomps[fc_h];
#else
	return bsearch(&(fc_code),
				   UnicodeDecompMain,
				   lengthof(UnicodeDecompMain),
				   sizeof(pg_unicode_decomposition),
				   fc_conv_compare);
#endif
}

/*
 * 获取给定代码点的组合类。
 */
static uint8 get_canonical_class(pg_wchar fc_code)
{
	const pg_unicode_decomposition *fc_entry = fc_get_code_entry(fc_code);

	/*
	 * 如果未找到任何条目，则使用的字符要么是韩文字母
	 * 要么是类为 0 且没有分解的字符。
	 */
	if (!fc_entry)
		return 0;
	else
		return fc_entry->comb_class;
}

/*
 * 根据先前查找的分解条目，获取分解后的字符。
 *
 * 注意：返回的指针可能指向静态分配的缓冲区，并且
 * 仅在下一次调用此函数之前有效！
 */
static const pg_wchar *
fc_get_code_decomposition(const pg_unicode_decomposition *fc_entry, int *fc_dec_size)
{
	static pg_wchar fc_x;

	if (DECOMPOSITION_IS_INLINE(fc_entry))
	{
		Assert(DECOMPOSITION_SIZE(fc_entry) == 1);
		fc_x = (pg_wchar) fc_entry->dec_index;
		*fc_dec_size = 1;
		return &fc_x;
	}
	else
	{
		*fc_dec_size = DECOMPOSITION_SIZE(fc_entry);
		return &UnicodeDecomp_codepoints[fc_entry->dec_index];
	}
}

/*
 * 计算给定字符将分解成多少个字符。
 *
 * 如果字符分解成的字符又可以分解，则需要递归。
 */
static int fc_get_decomposed_size(pg_wchar fc_code, bool fc_compat)
{
	const pg_unicode_decomposition *fc_entry;
	int			fc_size = 0;
	int			fc_i;
	const uint32 *fc_decomp;
	int			fc_dec_size;

	/*
	 * 对于未存储在表中的韩文字母的快速路径，以节省内存，因为
	 * 分解是算法性的。请参见
	 * https://www.unicode.org/reports/tr15/tr15-18.html，附录 10 获取详细信息。
	 */
	if (fc_code >= SBASE && fc_code < SBASE + SCOUNT)
	{
		uint32		fc_tindex,
					fc_sindex;

		fc_sindex = fc_code - SBASE;
		fc_tindex = fc_sindex % TCOUNT;

		if (fc_tindex != 0)
			return 3;
		return 2;
	}

	fc_entry = fc_get_code_entry(fc_code);

	/*
	 * 如果没有其他分解，则只计算当前代码。NULL 条目
	 * 相当于类为 0 且没有分解的字符。
	 */
	if (fc_entry == NULL || DECOMPOSITION_SIZE(fc_entry) == 0 ||
		(!fc_compat && DECOMPOSITION_IS_COMPAT(fc_entry)))
		return 1;

	/*
	 * 如果此条目还有其他分解代码，也要查看它们。首先
	 * 在可用表的列表中获取它的分解。
	 */
	fc_decomp = fc_get_code_decomposition(fc_entry, &fc_dec_size);
	for (fc_i = 0; fc_i < fc_dec_size; fc_i++)
	{
		uint32		fc_lcode = fc_decomp[fc_i];

		fc_size += fc_get_decomposed_size(fc_lcode, fc_compat);
	}

	return fc_size;
}

/*
 * 重新组合一组字符。对于韩文字母，计算
 * 是算法性的。对于其他字符，需要在分解
 * 表中进行反向查找。如果可以进行重新组合，则返回 true，否则返回 false。
 */
static bool fc_recompose_code(uint32 start, uint32 code, uint32 *result)
{
	/*
	 * 按照 Unicode 规范以算法方式处理韩文字母。
	 *
	 * 检查当前两个字符是否为 L 和 V。
	 */
	if (start >= LBASE && start < LBASE + LCOUNT &&
		code >= VBASE && code < VBASE + VCOUNT)
	{
		/* 制作 LV 形式的音节 */
		uint32		fc_lindex = start - LBASE;
		uint32		fc_vindex = code - VBASE;

		*result = SBASE + (fc_lindex * VCOUNT + fc_vindex) * TCOUNT;
		return true;
	}
	/* 检查当前两个字符是否为 LV 和 T */
	else if (start >= SBASE && start < (SBASE + SCOUNT) &&
			 ((start - SBASE) % TCOUNT) == 0 &&
			 code >= TBASE && code < (TBASE + TCOUNT))
	{
		/* 制作 LVT 形式的音节 */
		uint32		fc_tindex = code - TBASE;

		*result = start + fc_tindex;
		return true;
	}
	else
	{
		const pg_unicode_decomposition *entry;

		/*
		 * 进行分解表的反向查找以查看是否有任何匹配项。
		 * 比较只需在大小为 2 的子表中进行完美匹配，因为起始
		 * 字符已部分重新组合。此查找在后端代码中使用完美哈希函数。
		 */
#ifndef FRONTEND

		int			fc_h,
					fc_inv_lookup_index;
		uint64		fc_hashkey;
		pg_unicode_recompinfo fc_recompinfo = UnicodeRecompInfo;

		/*
		 * 计算哈希函数。哈希键是通过连接
		 * 两个代码点的字节按网络顺序形成的。另见
		 * src/common/unicode/generate-unicode_norm_table.pl。
		 */
		fc_hashkey = pg_hton64(((uint64) start << 32) | (uint64) code);
		fc_h = fc_recompinfo.hash(&fc_hashkey);

		/* 超出范围的结果表示没有匹配 */
		if (fc_h < 0 || fc_h >= fc_recompinfo.num_recomps)
			return false;

		fc_inv_lookup_index = fc_recompinfo.inverse_lookup[fc_h];
		entry = &UnicodeDecompMain[fc_inv_lookup_index];

		if (start == UnicodeDecomp_codepoints[entry->dec_index] &&
			code == UnicodeDecomp_codepoints[entry->dec_index + 1])
		{
			*result = entry->codepoint;
			return true;
		}

#else

		int			fc_i;

		for (fc_i = 0; fc_i < lengthof(UnicodeDecompMain); fc_i++)
		{
			entry = &UnicodeDecompMain[fc_i];

			if (DECOMPOSITION_SIZE(entry) != 2)
				continue;

			if (DECOMPOSITION_NO_COMPOSE(entry))
				continue;

			if (start == UnicodeDecomp_codepoints[entry->dec_index] &&
				code == UnicodeDecomp_codepoints[entry->dec_index + 1])
			{
				*result = entry->codepoint;
				return true;
			}
		}
#endif							/* !FRONTEND */
	}

	return false;
}

/*
 * 将给定代码分解到调用者提供的数组中。
 * 分解从调用者给出的当前位置开始，节省了在分解表上的一次查找。
 * 这里需要更新当前位置，以让调用者知道从哪里继续填充数组结果。
 */
static void fc_decompose_code(pg_wchar fc_code, bool fc_compat, pg_wchar **fc_result, int *fc_current)
{
	const pg_unicode_decomposition *fc_entry;
	int			fc_i;
	const uint32 *fc_decomp;
	int			fc_dec_size;

	/*
	 * 对于未存储在表中的韩文字母的快速路径，以节省内存，因为
	 * 分解是算法性的。请参见
	 * https://www.unicode.org/reports/tr15/tr15-18.html，附录 10 获取详细信息。
	 */
	if (fc_code >= SBASE && fc_code < SBASE + SCOUNT)
	{
		uint32		fc_l,
					fc_v,
					fc_tindex,
					fc_sindex;
		pg_wchar   *fc_res = *fc_result;

		fc_sindex = fc_code - SBASE;
		fc_l = LBASE + fc_sindex / (VCOUNT * TCOUNT);
		fc_v = VBASE + (fc_sindex % (VCOUNT * TCOUNT)) / TCOUNT;
		fc_tindex = fc_sindex % TCOUNT;

		fc_res[*fc_current] = fc_l;
		(*fc_current)++;
		fc_res[*fc_current] = fc_v;
		(*fc_current)++;

		if (fc_tindex != 0)
		{
			fc_res[*fc_current] = TBASE + fc_tindex;
			(*fc_current)++;
		}

		return;
	}

	fc_entry = fc_get_code_entry(fc_code);

	/*
	 * 如果没有可递归到的分解代码，就用当前分解进行填充。
	 * NULL 条目等效于类 0 且没有分解的字符，因此在这种情况下也无需填充。
	 */
	if (fc_entry == NULL || DECOMPOSITION_SIZE(fc_entry) == 0 ||
		(!fc_compat && DECOMPOSITION_IS_COMPAT(fc_entry)))
	{
		pg_wchar   *fc_res = *fc_result;

		fc_res[*fc_current] = fc_code;
		(*fc_current)++;
		return;
	}

	/*
	 * 如果该条目有其他分解代码，也要查看它们。
	 */
	fc_decomp = fc_get_code_decomposition(fc_entry, &fc_dec_size);
	for (fc_i = 0; fc_i < fc_dec_size; fc_i++)
	{
		pg_wchar	fc_lcode = (pg_wchar) fc_decomp[fc_i];

		/* 如果没有更多分解则离开 */
		fc_decompose_code(fc_lcode, fc_compat, fc_result, fc_current);
	}
}

/*
 * unicode_normalize - 将 Unicode 字符串规范化为指定形式。
 *
 * 输入是一个以 0 结束的代码点数组。
 *
 * 在前端，返回一个以 0 结束的代码点数组，使用 malloc 分配。
 * 如果内存不足，则返回 NULL。在后端，返回的字符串使用 palloc 
 * 进行分配，内存不足将通过 ereport() 报告。
 */
pg_wchar *
unicode_normalize(UnicodeNormalizationForm fc_form, const pg_wchar *fc_input)
{
	bool		fc_compat = (fc_form == UNICODE_NFKC || fc_form == UNICODE_NFKD);
	bool		fc_recompose = (fc_form == UNICODE_NFC || fc_form == UNICODE_NFKC);
	pg_wchar   *fc_decomp_chars;
	pg_wchar   *fc_recomp_chars;
	int			fc_decomp_size,
				fc_current_size;
	int			fc_count;
	const pg_wchar *fc_p;

	/* 重组的变量 */
	int			fc_last_class;
	int			fc_starter_pos;
	int			fc_target_pos;
	uint32		fc_starter_ch;

	/* 首先，进行字符分解 */

	/*
	 * 计算分解版本的字符长度。
	 */
	fc_decomp_size = 0;
	for (fc_p = fc_input; *fc_p; fc_p++)
		fc_decomp_size += fc_get_decomposed_size(*fc_p, fc_compat);

	fc_decomp_chars = (pg_wchar *) ALLOC((fc_decomp_size + 1) * sizeof(pg_wchar));
	if (fc_decomp_chars == NULL)
		return NULL;

	/*
	 * 现在递归填充每个条目。这需要第二次遍历分解表。
	 */
	fc_current_size = 0;
	for (fc_p = fc_input; *fc_p; fc_p++)
		fc_decompose_code(*fc_p, fc_compat, &fc_decomp_chars, &fc_current_size);
	fc_decomp_chars[fc_decomp_size] = '\0';
	Assert(fc_decomp_size == fc_current_size);

	/* 如果没有要分解的内容则离开 */
	if (fc_decomp_size == 0)
		return fc_decomp_chars;

	/*
	 * 现在应用规范顺序。
	 */
	for (fc_count = 1; fc_count < fc_decomp_size; fc_count++)
	{
		pg_wchar	fc_prev = fc_decomp_chars[fc_count - 1];
		pg_wchar	fc_next = fc_decomp_chars[fc_count];
		pg_wchar	fc_tmp;
		const uint8 fc_prevClass = get_canonical_class(fc_prev);
		const uint8 fc_nextClass = get_canonical_class(fc_next);

		/*
		 * 根据 Unicode (https://www.unicode.org/reports/tr15/tr15-18.html)
		 * 附录 4，字符串中两个相邻字符的序列是可交换对，
		 * 如果第一个字符的组合类（来自 Unicode 字符数据库）大于
		 * 第二个的组合类，并且第二个不是起始字符。
		 * 如果其组合类为 0，则字符为起始字符。
		 */
		if (fc_prevClass == 0 || fc_nextClass == 0)
			continue;

		if (fc_prevClass <= fc_nextClass)
			continue;

		/* 可以发生交换 */
		fc_tmp = fc_decomp_chars[fc_count - 1];
		fc_decomp_chars[fc_count - 1] = fc_decomp_chars[fc_count];
		fc_decomp_chars[fc_count] = fc_tmp;

		/* 回溯以再次检查 */
		if (fc_count > 1)
			fc_count -= 2;
	}

	if (!fc_recompose)
		return fc_decomp_chars;

	/*
	 * NFC 和 NFKC 的最后阶段是使用组合类重新组合重新排序的
	 * Unicode 字符串。重组字符串的长度不得超过分解字符串的长度，
	 * 因此输出字符串的分配基于这一假设。
	 */
	fc_recomp_chars = (pg_wchar *) ALLOC((fc_decomp_size + 1) * sizeof(pg_wchar));
	if (!fc_recomp_chars)
	{
		FREE(fc_decomp_chars);
		return NULL;
	}

	fc_last_class = -1;			/* 这消除了特殊检查 */
	fc_starter_pos = 0;
	fc_target_pos = 1;
	fc_starter_ch = fc_recomp_chars[0] = fc_decomp_chars[0];

	for (fc_count = 1; fc_count < fc_decomp_size; fc_count++)
	{
		pg_wchar	fc_ch = fc_decomp_chars[fc_count];
		int			fc_ch_class = get_canonical_class(fc_ch);
		pg_wchar	fc_composite;

		if (fc_last_class < fc_ch_class &&
			fc_recompose_code(fc_starter_ch, fc_ch, &fc_composite))
		{
			fc_recomp_chars[fc_starter_pos] = fc_composite;
			fc_starter_ch = fc_composite;
		}
		else if (fc_ch_class == 0)
		{
			fc_starter_pos = fc_target_pos;
			fc_starter_ch = fc_ch;
			fc_last_class = -1;
			fc_recomp_chars[fc_target_pos++] = fc_ch;
		}
		else
		{
			fc_last_class = fc_ch_class;
			fc_recomp_chars[fc_target_pos++] = fc_ch;
		}
	}
	fc_recomp_chars[fc_target_pos] = (pg_wchar) '\0';

	FREE(fc_decomp_chars);

	return fc_recomp_chars;
}

/*
 * 规范化“快速检查”算法；请参见
 * <http://www.unicode.org/reports/tr15/#Detecting_Normalization_Forms>
 */

/* 我们只在后端需要这个。 */
#ifndef FRONTEND

static const pg_unicode_normprops *
fc_qc_hash_lookup(pg_wchar fc_ch, const pg_unicode_norminfo *fc_norminfo)
{
	int			fc_h;
	uint32		fc_hashkey;

	/*
	 * 计算哈希函数。哈希键是具有网络顺序的字节的代码点。
	 */
	fc_hashkey = pg_hton32(fc_ch);
	fc_h = fc_norminfo->hash(&fc_hashkey);

	/* 超出范围的结果表示没有匹配 */
	if (fc_h < 0 || fc_h >= fc_norminfo->num_normprops)
		return NULL;

	/*
	 * 由于这是一个完美哈希，我们只需要与其标识的特定代码点匹配。
	 */
	if (fc_ch != fc_norminfo->normprops[fc_h].codepoint)
		return NULL;

	/* 成功！ */
	return &fc_norminfo->normprops[fc_h];
}

/*
 * 查找规范化快速检查字符属性
 */
static UnicodeNormalizationQC
fc_qc_is_allowed(UnicodeNormalizationForm fc_form, pg_wchar fc_ch)
{
	const pg_unicode_normprops *fc_found = NULL;

	switch (fc_form)
	{
		case UNICODE_NFC:
			fc_found = fc_qc_hash_lookup(fc_ch, &UnicodeNormInfo_NFC_QC);
			break;
		case UNICODE_NFKC:
			fc_found = fc_qc_hash_lookup(fc_ch, &UnicodeNormInfo_NFKC_QC);
			break;
		default:
			Assert(false);
			break;
	}

	if (fc_found)
		return fc_found->quickcheck;
	else
		return UNICODE_NORM_QC_YES;
}

UnicodeNormalizationQC
unicode_is_normalized_quickcheck(UnicodeNormalizationForm fc_form, const pg_wchar *fc_input)
{
	uint8		fc_lastCanonicalClass = 0;
	UnicodeNormalizationQC fc_result = UNICODE_NORM_QC_YES;

	/*
	 * 对于"D"形式，我们不运行快速检查。我们不包含这些的查找表，因为它们很大，检查这些特定形式的情况较少，并且对于"D"形式来说，运行慢路径比"C"形式要快，因为你不需要重新组合，这个过程是慢的。
	 */
	if (fc_form == UNICODE_NFD || fc_form == UNICODE_NFKD)
		return UNICODE_NORM_QC_MAYBE;

	for (const pg_wchar *fc_p = fc_input; *fc_p; fc_p++)
	{
		pg_wchar	fc_ch = *fc_p;
		uint8		fc_canonicalClass;
		UnicodeNormalizationQC fc_check;

		fc_canonicalClass = get_canonical_class(fc_ch);
		if (fc_lastCanonicalClass > fc_canonicalClass && fc_canonicalClass != 0)
			return UNICODE_NORM_QC_NO;

		fc_check = fc_qc_is_allowed(fc_form, fc_ch);
		if (fc_check == UNICODE_NORM_QC_NO)
			return UNICODE_NORM_QC_NO;
		else if (fc_check == UNICODE_NORM_QC_MAYBE)
			fc_result = UNICODE_NORM_QC_MAYBE;

		fc_lastCanonicalClass = fc_canonicalClass;
	}
	return fc_result;
}

#endif							/* !FRONTEND */
